|
In theoretical computer science, Almost Wide Probabilistic Polynomial-Time (AWPP) is a complexity class for problems in the context of quantum computing. AWPP contains the BQP (Bounded error, Quantum, Polynomial time) class, which contains the decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. In fact, it is the best known classical upper bound for BQP. Furthermore, it is contained in the APP class. ==References== 〔 * http://people.cs.uchicago.edu/~fortnow/papers/quantum.pdf Provides information on the connection between various complexity classes. * http://eccc.hpi-web.de/eccc-reports/2002/TR02-036/index.html Definition of AWPP and connection to APP and PP. * http://arxiv.org/abs/cs/9811023 Proof of BPQ in AWPP. * "Gap-definable counting classes" by S. Fenner, L. Fortnow, and S. Kurtz from the Journal of Computer and System Sciences. Pages 116-148, 1994, issue 48. Contains definitions. * "An oracle builder’s toolkit" by S. Fenner, L. Fortnow, S. Kurtz, and L. Li. in 8th IEEE Structure in Complexity Theory Conference Proceedings. Pages 120-131, 1993. Contains definitions. * (Complexity Zoo ): Contains a list of complexity classes, including AWPP, and their relation to other classes. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「AWPP (complexity)」の詳細全文を読む スポンサード リンク
|